I have solved the sudoku using JavaScript but I want to print -1 if the given sudoku has no solution. I have done it using recursion and have exhausted all the ways that I could think of. Please help me solve this question for unsolvable sudoko's.
let row = 0;
let col = 0;
let matrix = [
[0, 4, 0, 0, 0, 0, 1, 7, 9],
[0, 0, 2, 0, 0, 8, 0, 5, 4],
[0, 0, 6, 0, 0, 5, 0, 0, 8],
[0, 8, 0, 0, 7, 0, 9, 1, 0],
[0, 5, 0, 0, 9, 0, 0, 3, 0],
[0, 1, 9, 0, 6, 0, 0, 4, 0],
[3, 0, 0, 4, 0, 0, 7, 0, 0],
[5, 7, 0, 1, 0, 0, 2, 0, 0],
[9, 2, 8, 0, 0, 0, 0, 6, 0]
];
function sudoku(matrix, row, col) {
if (row == 9) {
console.log(matrix);
return;
}
let next_row = 0;
let next_col = 0;
if (col == 8) {
next_col = 0;
next_row = row + 1;
}
else {
next_col = col + 1;
next_row = row;
}
if (matrix[row][col] != 0) {
sudoku(matrix, next_row, next_col);
}
else {
for (let i = 0; i <= 9; i++) {
if (isSafe(matrix, row, col, i) == true) {
matrix[row][col] = i;
sudoku(matrix, next_row, next_col);
matrix[row][col] = 0;
}
}
}
}
function isSafe(matrix, row, col, value) {
for (let i = 0; i < matrix.length; i++) {
if (matrix[i][col] == value) {
return false;
}
}
for (let i = 0; i < matrix.length; i++) {
if (matrix[row][i] == value) {
return false;
}
}
let x = Math.floor(row / 3) * 3;
let y = Math.floor(col / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (matrix[x + i][y + j] == value) {
return false;
}
}
}
return true;
}
sudoku(matrix, row, col);
Example of sudoku with no solution:
let matrix = [
[0, 0, 0, 0, 5, 4, 3, 0, 6],
[0, 0, 0, 0, 0, 3, 2, 7, 0],
[0, 0, 0, 7, 2, 0, 0, 0, 1],
[9, 0, 0, 0, 7, 0, 0, 5, 3],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[8, 2, 0, 0, 1, 0, 0, 0, 9],
[3, 0, 0, 0, 6, 1, 0, 0, 0],
[0, 4, 6, 9, 0, 0, 0, 0, 0],
[7, 0, 1, 5, 4, 0, 0, 0, 6]
];
You can return false if the Sudoku is invalid and return true if it is valid.
let row = 0;
let col = 0;
let matrix = [
[0, 0, 0, 0, 5, 4, 3, 0, 6],
[0, 0, 0, 0, 0, 3, 2, 7, 0],
[0, 0, 0, 7, 2, 0, 0, 0, 1],
[9, 0, 0, 0, 7, 0, 0, 5, 3],
[0, 0, 0, 0, 0, 0, 0, 0, 0],
[8, 2, 0, 0, 1, 0, 0, 0, 9],
[3, 0, 0, 0, 6, 1, 0, 0, 0],
[0, 4, 6, 9, 0, 0, 0, 0, 0],
[7, 0, 1, 5, 4, 0, 0, 0, 6]
];
function sudoku(matrix, row, col) {
if (row == 9) {
console.log(matrix);
return true;
}
let next_row = 0;
let next_col = 0;
if (col == 8) {
next_col = 0;
next_row = row + 1;
} else {
next_col = col + 1;
next_row = row;
}
if (matrix[row][col] != 0) {
// Return the result from next empty box
return sudoku(matrix, next_row, next_col);
} else {
for (let i = 0; i <= 9; i++) {
if (isSafe(matrix, row, col, i) == true) {
matrix[row][col] = i;
// If found a valid sudoku, then return true. No need to check further.
if (sudoku(matrix, next_row, next_col)) return true;
matrix[row][col] = 0;
}
}
}
// No valid sudoku found after trying all numbers
return false;
}
function isSafe(matrix, row, col, value) {
for (let i = 0; i < matrix.length; i++) {
if (matrix[i][col] == value) {
return false;
}
}
for (let i = 0; i < matrix.length; i++) {
if (matrix[row][i] == value) {
return false;
}
}
let x = Math.floor(row / 3) * 3;
let y = Math.floor(col / 3) * 3;
for (let i = 0; i < 3; i++) {
for (let j = 0; j < 3; j++) {
if (matrix[x + i][y + j] == value) {
return false;
}
}
}
return true;
}
const isValid = sudoku(matrix, row, col);
console.log(isValid ? "Valid Sudoku" : "Ivalid Sudoku");